package leetcode;

public class Code33 {
    public static void main(String[] args) {
        System.out.println(new Code33().search(new int[]{4,5,6,7,0,1,2},5));
    }
    public int search(int[] nums, int target) {
        return find(nums,0,nums.length-1,target);
    }

    public int find(int[] nums,int start,int end , int target){
        if(start>end){
            return -1;
        }
        int index = nums[(start+end)/2];
        if(target>index){
            if(index>nums[end]){
                return find(nums,(start+end)/2+1,end,target);
            }else{
                int right= find(nums,(start+end)/2+1,end,target);
                if(right!=-1){
                    return right;
                }
                int left = find(nums,start,(start+end)/2-1,target);
                return left;
            }
        }else if(target<index){
            if(index>nums[end]){
                int right= find(nums,(start+end)/2+1,end,target);
                if(right!=-1){
                    return right;
                }
                int left = find(nums,start,(start+end)/2-1,target);
                return left;
            }else{
                return find(nums,start,(start+end)/2-1,target);
            }
        }else{
            return (start+end)/2;
        }
    }
}
